# 两个数组的交集II： https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        """ 排序加双指针,和 349是一样的，不过是结果及内匹配的元素可以重复"""
        nums1.sort()
        nums2.sort()
        i = j = 0
        rst = list()
        
        while i < len(nums1) and j < len(nums2):
            if nums1[i] == nums2[j]:
                rst.append(nums1[i])
                i += 1
                j += 1
            elif nums1[i] < nums2[j]:
                i += 1
            else:
                j += 1

        return rst    


class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        """     
            hash的解法， 使用hash记录元素，并且记录元素出现的次数， 比较两个数组中，同一元素出现最小的次数，加入到结果集
        """
        hashMap1 = dict()
        hashMap2 = dict()
        for num in nums1: hashMap1[num] = hashMap1.get(num, 0) + 1
        for num in nums2: hashMap2[num] = hashMap2.get(num, 0) + 1
        
        rst = []
        for key in hashMap1:
            if key in hashMap2: 
                for i in range(min(hashMap1[key], hashMap2[key])):
                    rst.append(key)
        
        return rst


"""
进阶：

如果给定的数组已经排好序呢？你将如何优化你的算法？
使用双指针

如果 nums1 的大小比 nums2 小很多，哪种方法更优？
使用hash表， 小的hash， 大的顺序遍历查找

如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
具体没有讲， 就是外部排序 加上双指针

"""
